package algorithm.sort;

import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

public class QuickSortDemo2 {

  //快速排序
  int[] arr = {2, 1, 3};

  @Before
  public void before() {
    int[] arr = new int[10];
    for (int i = 0; i < 10; i++) {
      int i1 = new Random().nextInt(100);
      arr[i] = i1;
    }
    this.arr = arr;
  }

  @Test
  public void test() {
    System.out.println(Arrays.toString(this.arr));
    quickSort(0, this.arr.length - 1);
    System.out.println(Arrays.toString(this.arr));
  }

  /*
  快速排序
    确定一个数值作为基准值， 通过左右指针 遍历这些元素的数值，把大于基准的数值和小于基准的数值的指针元素互换，
    这样遍历直到左右指针碰撞之后，把基准值放到指针碰撞的位置，这样就是快排的第一轮排序， 这样的排序结果
    会是的原来无序的元素 中轴 左边的元素都小于中轴  右边的元素都大于中轴，
   */
  public int quickSort(int low, int high) {
    if (low >= high) {
      return low;
    }

    int i = low;
    int j = high;

    int tmp = this.arr[low];
    while (true) {

      // i<j i>k 这个过程很巧  这个地方可以用 【3，2】 【2，3】来试验
      for (; i < j; i++) {
        if (this.arr[i] > tmp) {
          break;
        }
      }

      // j<=k 这个过程很巧  这个地方可以用 【3，2】 【2，3】来试验
      for (; ; j--) {
        if (this.arr[j] <= tmp) {
          break;
        }
      }
      if (j <= i) {
        //说明指针碰撞了 必须用j 和 基准值
        exchange(low, j);
        break;
      } else {
        //素组互换元素
        exchange(i, j);
      }
    }
//    j是中轴
    quickSort(low, j - 1);
    quickSort(j + 1, high);
    return j;
  }

  @Test
  public void test2() {
    //快速排序
    int[] arr = {3, 2};
    quickSort(arr, 0, 1);
  }

  //网上的一个方法 这个递归调用 很有借鉴价值
  public static void quickSort(int[] a, int low, int high) {

    // 递归出口
    if (low > high) {
      return;
    }
    //标记
    int i = low;
    int j = high;
    int key = a[low];

    // 完成一趟快排
    while (i < j) {
      // 1.从右往左找到第一个小于key的数
      while (i < j && a[j] > key) {
        j--;
      }
      // 2. 从左往右找到第一个大于key的数
      //(刚开始少了等于，发现run了好久都没run出来，可能陷入了死循环)
      while (i < j && a[i] <= key) {
        i++;
      }
      // 3. 交换
      if (i < j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
      }

    }

    // 4.调整key的位置 (将key放到i的位置)
    a[low] = a[i];
    a[i] = key;

    // 递归过程
    // 5. 对key左边的数快排
    quickSort(a, low, i - 1);
    // 6. 对key右边的数快排
    quickSort(a, i + 1, high);
  }

  public void exchange(int a, int b) {
    //两个元素排序
    if (this.arr[a] > this.arr[b]) {
      int temp = this.arr[a];
      this.arr[a] = this.arr[b];
      this.arr[b] = temp;
    }
  }

}
